// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现类型统一。

package types2

import (
	"bytes"
	"fmt"
	"strings"
)

// unifier维护两组独立的类型参数x和y 
// 用于解析提供给UNIFED调用的x和y参数
// 中的类型参数。对于单向统一，只提供其中一个集合（比如x），然后类型参数是
// 只为传递给UNIFED的x参数解析，而不是y参数
// （即使它也可能包含相同的类型参数）。这个
// 对于推断自递归调用的类型参数至关重要：
// 
// func f[P any]（a P）{f（a）}
// 
// 对于调用f（a），我们想推断P的类型参数是P。
// 在统一过程中，参数类型P必须解析为
// 参数P（“x”侧），但是参数类型P必须单独存在，以便统一将类型参数P解析为P。对于双向统一，两个集合都提供。这使得
// 统一可以从参数类型转换为参数类型，反之亦然。
// 对于约束类型推断，我们使用双向统一
// 其中x和y类型参数相同。这是通过设置其中一个（使用init），然后将其值
// 分配给另一个来实现的。

const (
	// 递归深度的上限。用于捕获由于实现问题（例如，请参阅问题#48619，#48656）而导致的无限递归。
	unificationDepthLimit = 50

	// 达到统一深度限制时是否恐慌。当
	// 研究无限递归时打开。ABCFDG＊＊＊＊＊＊＊／／如果设置EnabeCraceType统一，统一将考虑ABCFDG＊＊＊＊＊＊/ /非本地（未绑定）类型参数的核心类型（如果有的话）。
	panicAtUnificationDepthLimit = false

	enableCoreTypeUnification = true

	// 如果设置了traceInference，unification将打印其操作的跟踪。
	// 痕迹解释：
	// x≡ 试图统一x型和y型
	// p➞ y类型参数p被设置为y类型（p被推断为y）
	// p⇄ q类型参数p和q匹配（p被推断为q，反之亦然）
	// x≢ y型x和y不能统一为
	// /[p，q，…]➞ [x，y，…]从类型参数映射到类型
	traceInference = false
)

// 统一器维护x和y 
// 的当前类型参数，以及为每个类型参数推断的相应类型。
// 通过调用newUnifier创建unifier。
type unifier struct {
	exact bool
	x, y  tparamsList // x和y必须通过tparamsList初始化。init 
	types []Type      // 由x和y共享的推断类型
	depth int         // 统一期间的递归深度
}

// newUnifier返回一个新的unifier。
// 如果设置了exact，则统一要求统一类型与
// 完全匹配。如果未设置exact，则如果统一失败，则会考虑命名类型的基础类型
// 并忽略通道的
// 方向。
// TODO（gri）exact不再由调用者设置。考虑移除它。
func newUnifier(exact bool) *unifier {
	u := &unifier{exact: exact}
	u.x.unifier = u
	u.y.unifier = u
	return u
}

// unify尝试统一x和y，并报告是否成功。
func (u *unifier) unify(x, y Type) bool {
	return u.nify(x, y, nil)
}

func (u *unifier) tracef(format string, args ...interface{}) {
	fmt.Println(strings.Repeat(".  ", u.depth) + sprintf(nil, true, format, args...))
}

// tparamsList描述了类型参数列表以及为其推断的类型。
type tparamsList struct {
	unifier *unifier
	tparams []*TypeParam
	// 对于每个tparams元素，索引中都有一个对应的类型槽索引。
	// 索引<0:统一。types[-index-1]==nil 
	// index==0:尚未分配类型槽
	// index>0:unifier。类型[index-1]==typ 
	// 连接的tparams元素共享相同的类型槽，因此具有相同的索引。
	// 通过对nil类型使用负索引，我们不需要检查unifier。输入
	// 查看是否有类型。
	indices []int // len（d.index）=len（d.tparams）
}

// String返回tparamsList的字符串表示形式。用于调试。
func (d *tparamsList) String() string {
	var buf bytes.Buffer
	w := newTypeWriter(&buf, nil)
	w.byte('[')
	for i, tpar := range d.tparams {
		if i > 0 {
			w.string(", ")
		}
		w.typ(tpar)
		w.string(": ")
		w.typ(d.at(i))
	}
	w.byte(']')
	return buf.String()
}

// init使用给定的类型参数初始化d。
// 类型参数必须按照它们在声明中出现的顺序
// （这确保tparams索引与相应的类型参数索引匹配）。
func (d *tparamsList) init(tparams []*TypeParam) {
	if len(tparams) == 0 {
		return
	}
	if debug {
		for i, tpar := range tparams {
			assert(i == tpar.index)
		}
	}
	d.tparams = tparams
	d.indices = make([]int, len(tparams))
}

// join将x的第i个类型参数与y的第j个类型参数统一起来。
// 如果两个类型参数已经有一个关联的类型，并且它们是
// 未联接，join将失败并返回false。
func (u *unifier) join(i, j int) bool {
	if traceInference {
		u.tracef("%s ⇄ %s", u.x.tparams[i], u.y.tparams[j])
	}
	ti := u.x.indices[i]
	tj := u.y.indices[j]
	switch {
	case ti == 0 && tj == 0:
		// 两个类型参数都没有与之关联的类型槽。
		// 分配一个新的联接的nil类型插槽（负索引）。
		u.types = append(u.types, nil)
		u.x.indices[i] = -len(u.types)
		u.y.indices[j] = -len(u.types)
	case ti == 0:
		// x的类型参数还没有类型槽。使用y的插槽。
		u.x.indices[i] = tj
	case tj == 0:
		// y的类型参数还没有类型插槽。使用x的slot.
		u.y.indices[j] = ti

	// 两个类型参数都有一个slot:ti！=0&&tj！=0.
	case ti == tj:
		// 两个类型参数已共享同一个插槽。无事可做。
		break
	case ti > 0 && tj > 0:
		// 两个类型参数都有推断类型（可能不同）。无法加入。
		// TODO（gri）我们应该检查类型是否相同吗？侦查
		return false
	case ti > 0:
		// 只有x的类型参数具有推断类型。将x插槽用于y.
		u.y.setIndex(j, ti)
	// 此案例的处理方式与默认案例相同。
	// case tj>0:
	// 
	// u.x.setIndex（i，tj）
	default:
		// 两个类型参数都没有推断类型。用y槽代替x 
		// （或者用x槽代替y，这无关紧要）。
		u.x.setIndex(i, tj)
	}
	return true
}

// 如果typ是d的类型参数，则index返回类型参数index。
// 否则，结果为<0。
func (d *tparamsList) index(typ Type) int {
	if tpar, ok := typ.(*TypeParam); ok {
		return tparamIndex(d.tparams, tpar)
	}
	return -1
}

// 如果tpar是列表中的类型参数，tparamIndex将返回类型参数索引。
// 否则，结果为<0。tpar不得为零。
func tparamIndex(list []*TypeParam, tpar *TypeParam) int {
	// 一旦绑定了类型参数，其索引就>=0。但是，有一些代码路径（即跟踪和类型散列）可以使用未绑定的类型参数到达这里，因此下面检查0<=i的
	// 代码路径。
	// TODO（rfindley）：研究一种更好的方法来防止使用
	// 未绑定的类型参数。
	if i := tpar.index; 0 <= i && i < len(list) && list[i] == tpar {
		return i
	}
	return -1
}

// setIndex将第i个类型参数
// （及其所有关联参数）的类型槽索引设置为tj。类型参数
// 必须有一个与之关联的（可能为nil）类型插槽。xiao zhong
func (d *tparamsList) setIndex(i, tj int) {
	ti := d.indices[i]
	assert(ti != 0 && tj != 0)
	for k, tk := range d.indices {
		if tk == ti {
			d.indices[k] = tj
		}
	}
}

func (d *tparamsList) at(i int) Type {
	if ti := d.indices[i]; ti > 0 {
		return d.unifier.types[ti-1]
	}
	return nil
}

// set设置第i个类型参数的类型类型；
// 类型不能为零，也不能在之前设置过。
func (d *tparamsList) set(i int, typ Type) {
	assert(typ != nil)
	u := d.unifier
	if traceInference {
		u.tracef("%s ➞ %s", d.tparams[i], typ)
	}
	switch ti := d.indices[i]; {
	case ti < 0:
		u.types[-ti-1] = typ
		d.setIndex(i, -ti)
	case ti == 0:
		u.types = append(u.types, typ)
		d.indices[i] = len(u.types)
	default:
		panic("type already set")
	}
}

// unknowns返回尚未设置类型的类型参数数。
func (d *tparamsList) unknowns() int {
	n := 0
	for _, ti := range d.indices {
		if ti <= 0 {
			n++
		}
	}
	return n
}

// types返回类型参数
// 的推断类型列表（通过统一）和索引。如果推断出所有类型，则返回的索引小于0。
// 否则为第一个无法推断的类型参数的索引；
// 即列表[index]为零。
func (d *tparamsList) types() (list []Type, index int) {
	list = make([]Type, len(d.tparams))
	index = -1
	for i := range d.tparams {
		t := d.at(i)
		list[i] = t
		if index < 0 && t == nil {
			index = i
		}
	}
	return
}

func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
	return x == y || u.nify(x, y, p)
}

// nify实现了核心统一算法，这是一个
// Checker的改编版本。完全相同的对于
// 代码的更改，应在此处进行相应的更改。
// 不能直接从unifier外部调用。
func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) {
	if traceInference {
		u.tracef("%s ≡ %s", x, y)
	}

	// 在统一失败的情况下采取权宜之计。ABCFDG 
	if u.depth >= unificationDepthLimit {
		if traceInference {
			u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
		}
		if panicAtUnificationDepthLimit {
			panic("unification reached recursion depth limit")
		}
		return false
	}
	u.depth++
	defer func() {
		u.depth--
		if traceInference && !result {
			u.tracef("%s ≢ %s", x, y)
		}
	}()

	if !u.exact {
		// （我们使用！hasName排除任何带有名称的类型，包括
		// 基本类型和类型参数；其余为未命名类型。）
		if nx, _ := x.(*Named); nx != nil && !hasName(y) {
			if traceInference {
				u.tracef("under %s ≡ %s", nx, y)
			}
			return u.nify(nx.under(), y, p)
		} else if ny, _ := y.(*Named); ny != nil && !hasName(x) {
			if traceInference {
				u.tracef("%s ≡ under %s", x, ny)
			}
			return u.nify(x, ny.under(), p)
		}
	}

	// x或y中至少有一个是类型参数的情况。
	switch i, j := u.x.index(x), u.y.index(y); {
	case i >= 0 && j >= 0:
		// x和y都是类型参数
		if u.join(i, j) {
			return true
		}
		// x和y都有推断类型-它们必须匹配
		return u.nifyEq(u.x.at(i), u.y.at(j), p)

	case i >= 0:
		// x是类型参数，y不是
		if tx := u.x.at(i); tx != nil {
			return u.nifyEq(tx, y, p)
		}
		// 否则，从y推断类型
		u.x.set(i, y)
		return true

	case j >= 0:
		// y是类型参数，x不是
		if ty := u.y.at(j); ty != nil {
			return u.nifyEq(x, ty, p)
		}
		// 否则，从x 
		u.y.set(j, x)
		return true
	}

	// 推断类型如果我们到这里，x或y是一个类型参数，那么它们是我们声明列表之外的类型参数
	// 。尝试统一它们的核心类型，如果有
	// （有关测试用例，请参阅第#50755期）。
	if enableCoreTypeUnification && !u.exact {
		if isTypeParam(x) && !hasName(y) {
			// 在考虑统一的类型参数时
			// 我们看一下调整后的核心术语（调整后的核心类型
			// 带有波浪号信息）。
			// 如果调整后的核心类型是命名类型N；
			// 对应的核心类型在（N）下。自从u、 确切的
			// 而y没有名字，统一将以
			// 结尾，比较（N）到y，所以我们可以使用核心
			// 类型。我们可以忽略tilde，因为我们已经看到了两边的基本类型，两边都有已知的类型。
			// 优化。
			if cx := coreType(x); cx != nil {
				if traceInference {
					u.tracef("core %s ≡ %s", x, y)
				}
				return u.nify(cx, y, p)
			}
		} else if isTypeParam(y) && !hasName(x) {
			// 参见上面的注释
			if cy := coreType(y); cy != nil {
				if traceInference {
					u.tracef("%s ≡ core %s", x, y)
				}
				return u.nify(x, cy, p)
			}
		}
	}

	// 对于类型统一，不要为相同的
	// 类型。相反，要在元素方面对它们进行比较，以统一
	// 匹配（以及相等的类型参数类型）。一个简单的测试用例
	// 其中重要的是：func f[P any]（ap）{f（A）}。

	switch x := x.(type) {
	case *Basic:
		// 除了符文和字节
		// 别名之外，基本类型都是单例，因此我们不能只依赖上面的x==y检查
		// 。另请参见TypeName中的注释。伊莎莉亚。
		if y, ok := y.(*Basic); ok {
			return x.kind == y.kind
		}

	case *Array:
		// 如果两个数组类型的元素类型相同，且数组长度相同，则它们是相同的。
		if y, ok := y.(*Array); ok {
			// 如果由于某些错误，一个或两个数组长度未知（<0），则
			// 假定它们是相同的，以避免出现虚假的后续错误。
			return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p)
		}

	case *Slice:
		// 如果两个切片类型具有相同的元素类型，则它们是相同的。
		if y, ok := y.(*Slice); ok {
			return u.nify(x.elem, y.elem, p)
		}

	case *Struct:
		// 如果两个结构类型具有相同的字段序列，则它们是相同的，
		// 如果相应的字段具有相同的名称和相同的类型，则
		// 和相同的标记。两个嵌入字段被认为具有相同的
		// 名称。不同包中的小写字段名称总是不同的。
		if y, ok := y.(*Struct); ok {
			if x.NumFields() == y.NumFields() {
				for i, f := range x.fields {
					g := y.fields[i]
					if f.embedded != g.embedded ||
						x.Tag(i) != y.Tag(i) ||
						!f.sameId(g.pkg, g.name) ||
						!u.nify(f.typ, g.typ, p) {
						return false
					}
				}
				return true
			}
		}

	case *Pointer:
		// 如果两个指针类型具有相同的基类型，则它们是相同的。
		if y, ok := y.(*Pointer); ok {
			return u.nify(x.base, y.base, p)
		}

	case *Tuple:
		// 如果两个元组的元素数相同，则它们的类型相同
		// 并且相应的元素具有相同的类型。
		if y, ok := y.(*Tuple); ok {
			if x.Len() == y.Len() {
				if x != nil {
					for i, v := range x.vars {
						w := y.vars[i]
						if !u.nify(v.typ, w.typ, p) {
							return false
						}
					}
				}
				return true
			}
		}

	case *Signature:
		// 如果两个函数类型具有相同数量的参数
		// 并且结果值、相应的参数和结果类型相同，
		// 并且两个函数要么是可变的，要么都不是。参数和结果
		// 名称不需要匹配。
		// TODO（gri）处理类型参数或记录为什么我们可以忽略它们。
		if y, ok := y.(*Signature); ok {
			return x.variadic == y.variadic &&
				u.nify(x.params, y.params, p) &&
				u.nify(x.results, y.results, p)
		}

	case *Interface:
		// 如果两个接口类型的方法集与
		// 相同的名称和相同的函数类型，则它们是相同的。
		// 不同的包总是不同的。这些方法的顺序无关紧要。
		if y, ok := y.(*Interface); ok {
			xset := x.typeSet()
			yset := y.typeSet()
			if xset.comparable != yset.comparable {
				return false
			}
			if !xset.terms.equal(yset.terms) {
				return false
			}
			a := xset.methods
			b := yset.methods
			if len(a) == len(b) {
				// 接口类型是唯一可以发生循环的类型
				// 没有通过命名类型“终止”；这种循环只能通过方法参数类型创建，这些参数类型是嵌入当前接口的匿名接口（直接或间接）。示例：
				// 
				// 类型T接口{
				// m（）接口{T}
				// }
				// /
				// 如果比较两个这样的（不同名称的）接口，
				// 如果没有检测到循环，将发生无休止的递归。
				// 
				// 如果之前比较过x和y，它们必须等于
				// （如果不是，则递归将停止）；
				// 在ifacePair堆栈中搜索同一对。
				// 
				// 这是一个二次算法，但在实践中，这些堆栈
				// 非常短（以接口
				// 的嵌套深度为界，通过参数类型重复出现类型声明，这是非常罕见的
				// 情况）。另一种实现可能会使用
				// /“已访问”映射，但总体而言，这可能效率较低。
				q := &ifacePair{x, y, p}
				for p != nil {
					if p.identical(q) {
						return true // 在
					}
					p = p.prev
				}
				if debug {
					assertSortedMethods(a)
					assertSortedMethods(b)
				}
				for i, f := range a {
					g := b[i]
					if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
						return false
					}
				}
				return true
			}
		}

	case *Map:
		// 之前对同一对进行了比较。如果两个映射类型具有相同的键和值类型，则它们是相同的。
		if y, ok := y.(*Map); ok {
			return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p)
		}

	case *Chan:
		// 如果两个通道类型具有相同的值类型，则它们是相同的。
		if y, ok := y.(*Chan); ok {
			return (!u.exact || x.dir == y.dir) && u.nify(x.elem, y.elem, p)
		}

	case *Named:
		// TODO（gri）此代码现在与Checker中的并行代码不同。完全相同的侦查
		if y, ok := y.(*Named); ok {
			xargs := x.targs.list()
			yargs := y.targs.list()

			if len(xargs) != len(yargs) {
				return false
			}

			// TODO（gri）这并不总是正确的：如果其中一个嵌套在函数中，则两个类型可能在同一个包中具有相同的名称
			// 。
			// 可能性极低，但我们需要一个始终正确的解决方案。
			if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
				for i, x := range xargs {
					if !u.nify(x, yargs[i], p) {
						return false
					}
				}
				return true
			}
		}

	case *TypeParam:
		// 两个类型参数（不属于
		// 封闭类型的类型参数的一部分，如本函数开头所述）
		// 如果它们来自同一声明，则它们是相同的。
		return x == y

	case nil:
		// 避免在无类型

	default:
		panic(sprintf(nil, true, "u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams))
	}

	return false
}
